#include <stdio.h>
#include <stdlib.h>
#include <string.h>


typedef void* DataType;          // 通用数据类型
typedef void (*free_kvPair)(void* k, void* v);  // 释放函数类型



/*---------- 数据结构定义 ----------*/

// 哈希表节点
typedef struct kvPair {
    void *key;          // 键指针
    void *value;        // 值指针
    struct kvPair *next;  // 下一个节点
} kvPair;

// 哈希表结构
typedef struct {
    kvPair **buckets;   // kv桶
    size_t capacity;    // 总容量
    size_t size;        // 当前元素数量
    size_t keySize;    // 键类型大小
    size_t valueSize;  // 值类型大小
    /*hashMap函数指针*/

    unsigned long (*hash_func)(const void *key);            // 哈希函数
    int (*key_compare)(const void *key1, const void *key2); // 键比较函数
    void (*key_free)(void *key);                            // 键释放函数
    void (*value_free)(void *value);                        // 值释放函数
} HashMap;

// 邻接表
typedef struct AdjTable {
    void*           dest;
    struct AdjTable *next;
} AdjTable;

// topo节点
typedef struct TopoNode {
    DataType data;      // 节点数据
    int indegree;               // 入度值（原始）
    AdjTable *adj;              // 邻接表
} TopoNode;

// topo排序结果
typedef struct  TopoResult{
    DataType* order;        // 排序结果数组
    int* batches;           // 批次标记数组
    size_t size;            // 结果总数
    int totalBatches;       // 总批次数
} TopoResult;

typedef struct  batchResult {
    DataType*   data;            // 节点数组
    int count;                   // 节点数量
    int batch;                   // 批次号
    struct batchResult* next;
} BatchResult;


// 默认哈希函数（整数或指针）
static unsigned long default_hash_func(const void *key) {
    return (unsigned long)key;
}

// 默认键比较函数
static int default_key_compare(const void *key1, const void *key2) {
    return key1 == key2;
}

// 创建哈希表
HashMap* hashmap_create(
    size_t capacity,
    size_t keySize,
    size_t valueSize,
    unsigned long (*hash_func)(const void *),
    int (*key_compare)(const void *, const void *),
    void (*key_free)(void *),
    void (*value_free)(void *)
) {
    HashMap *map = malloc(sizeof(HashMap));
    if (!map) return NULL;
    
    // 初始容量调整为最接近的2的幂
    size_t initCapacity = 8;
    while (initCapacity < capacity) initCapacity <<= 1;
    
    map->buckets = calloc(initCapacity, sizeof(kvPair *));
    if (!map->buckets) {
        free(map);
        return NULL;
    }
    map->capacity = capacity;
    map->size = 0;
    map->keySize = keySize;
    map->valueSize = valueSize;
    map->hash_func = hash_func ? hash_func : default_hash_func;
    map->key_compare = key_compare ? key_compare : default_key_compare;
    map->key_free = key_free;
    map->value_free = value_free;
    return map;
}

// 释放节点内存
static void free_kvPeer(HashMap *map, kvPair *kv) {
    if (map->key_free) map->key_free(kv->key);
    if (map->value_free) map->value_free(kv->value);
    // free(kv->key);
    // free(kv->value);
    free(kv);
}



// 扩容哈希表
static void resize_hashmap(HashMap *map, size_t new_capacity) {
    kvPair **new_buckets = calloc(new_capacity, sizeof(kvPair *));
    if (!new_buckets) return;
    
    // 重新插入所有元素
    for (size_t i = 0; i < map->capacity; i++) {
        kvPair *current = map->buckets[i];
        while (current) {
            kvPair *next = current->next;
            
            // 计算新位置
            size_t new_index = map->hash_func(current->key) & (new_capacity - 1);
            
            // 插入新桶
            current->next = new_buckets[new_index];
            new_buckets[new_index] = current;
            
            current = next;
        }
    }
    
    free(map->buckets);
    map->buckets = new_buckets;
    map->capacity = new_capacity;
}

// 插入键值对
int hashmap_put(HashMap *map, const void *key, const void *value) {
    if (!map || !key) return 0;
    
    // 检查是否需要扩容（负载因子 > 0.75）
    if (map->size >= map->capacity * 0.75) {
        resize_hashmap(map, map->capacity << 1);
    }
    
    size_t index = map->hash_func(key) & (map->capacity - 1);
    kvPair *current = map->buckets[index];
    
    // 检查键是否已存在
    while (current) {
        if (map->key_compare(current->key, key)) {
            // 更新值
            if (map->value_free) map->value_free(current->value);
            if (map->valueSize > 0) {
                memcpy(current->value, value, map->valueSize);
            } else {
                current->value = (void *)value;
            }
            return 1;
        }
        current = current->next;
    }
    
    // 创建新节点
    kvPair *new_kv = malloc(sizeof(kvPair));
    if (!new_kv) return 0;
    
    // 分配键内存
    if (map->keySize > 0) {
        new_kv->key = malloc(map->keySize);
        memcpy(new_kv->key, key, map->keySize);
    } else {
        new_kv->key = (void *)key;
    }
    
    // 分配值内存
    if (map->valueSize > 0) {
        new_kv->value = malloc(map->valueSize);
        memcpy(new_kv->value, value, map->valueSize);
    } else {
        new_kv->value = (void *)value;
    }
    
    // 插入链表头部
    new_kv->next = map->buckets[index];
    map->buckets[index] = new_kv;
    map->size++;
    return 1;
}

// 查找键
void* hashmap_get(HashMap *map, const void *key) {
    if (!map || !key) return NULL;
    
    size_t index = map->hash_func(key) & (map->capacity - 1);
    kvPair *current = map->buckets[index];
    
    while (current) {
        if (map->key_compare(current->key, key)) {
            return current->value;
        }
        current = current->next;
    }
    
    return NULL;
}

// 删除键
int hashmap_remove(HashMap *map, const void *key, free_kvPair free_kv) {
    if (!map || !key) return 0;
    
    size_t index = map->hash_func(key) & (map->capacity - 1);
    kvPair *current = map->buckets[index];
    kvPair *prev = NULL;
    
    while (current) {
        if (map->key_compare(current->key, key)) {
            if (prev) {
                prev->next = current->next;
            } else {
                map->buckets[index] = current->next;
            }
            free_kvPeer(map, current);
            map->size--;
            return 1;
        }
        
        prev = current;
        current = current->next;
    }
    
    return 0;
}

// 销毁哈希表
void hashmap_destroy(HashMap *map) {
    if (!map) return;
    
    for (size_t i = 0; i < map->capacity; i++) {
        kvPair *current = map->buckets[i];
        while (current) {
            kvPair *next = current->next;
            free_kvPeer(map, current);
            current = next;
        }
    }
    
    free(map->buckets);
    free(map);
}


// 整数哈希函数
unsigned long int_hash(const void *key) {
    int k = *(int *)key;
    k = ((k >> 16) ^ k) * 0x45d9f3b;
    k = ((k >> 16) ^ k) * 0x45d9f3b;
    return (unsigned int)((k >> 16) ^ k);
}

// 整数键比较
int int_compare(const void *key1, const void *key2) {
    return *(int *)key1 == *(int *)key2;
}

// 字符串哈希函数 (djb2)
unsigned long string_hash(const void *key) {
    const char *str = (const char *)key;
    unsigned long hash = 5381;
    int c;
    while ((c = *str++)) {
        hash = ((hash << 5) + hash) + (unsigned long)c; /* hash * 33 + c */
    }
    return hash;
}

// 字符串比较
int string_compare(const void *key1, const void *key2) {
    return strcmp((const char *)key1, (const char *)key2) == 0;
}


/*---------- 队列操作 ----------*/

typedef struct QueueNode {                
    DataType data;                      
    struct QueueNode* next;
} QueueNode;

typedef struct {
    QueueNode* front;
    QueueNode* rear;
    int count;              // 队列元素计数
} Queue;

// 创建队列
Queue* createQueue() {
    Queue* q = (Queue*)malloc(sizeof(Queue));
    q->front = q->rear = NULL;
    q->count = 0;
    return q;
}

// 入队
void enqueue(Queue* q, DataType data) {
    QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));
    newNode->data = data;
    newNode->next = NULL;

    if (q->rear) {
        q->rear->next = newNode;
        q->rear = newNode;
    } else {
        q->front = q->rear = newNode;
    }
    q->count++;
}
// 出队
DataType dequeue(Queue* q) {
    if (!q->front) return NULL;

    QueueNode* temp = q->front;
    DataType data = temp->data;

    q->front = q->front->next;
    if (!q->front) q->rear = NULL;
    
    free(temp);
    q->count--;
    return data;
}
// 队列是否为空
int isEmpty(Queue* q) {
    return q->count == 0;
}

// hashmap建立依赖关系
int addDependence(HashMap* graph, const void*  srcKey, const void* destKey) {
    TopoNode* srcNode = hashmap_get(graph, srcKey); 
    TopoNode* destNode = hashmap_get(graph, destKey);
    if ( !srcNode || !destNode || !srcNode->data || !destNode->data) 
    {
        return 0;
    }
    AdjTable* newAdj = (AdjTable*)malloc(sizeof(AdjTable));
    newAdj->dest = (void*)destKey;
    newAdj->next = srcNode->adj;
    srcNode->adj = newAdj;
    destNode->indegree++;
    return 1;
}

// 计算拓扑排序
int topoSort(HashMap* graph, TopoResult* result) {
    if (graph->size == 0) return -1;

    Queue* queue = createQueue();
    DataType* order = (DataType*)malloc(graph->size * sizeof(DataType));
    int* batches = (int*)malloc(graph->size * sizeof(int));
    size_t count = 0;
    int currentBatch = 0;

    // 初始化队列
    for (size_t i = 0; i < graph->capacity; i++) {
        kvPair* current = graph->buckets[i];
        while (current) {
            TopoNode* node = (TopoNode*)current->value;
            if (node->data&&node->indegree == 0) {
                enqueue(queue, current->key);
            }
            current = current->next;
        }
    }
    // 入队   
    while (!isEmpty(queue)) {
        int levelSize = queue->count;
        for (int i = 0; i < levelSize; i++) {
            DataType k = dequeue(queue);
            TopoNode* node = (TopoNode*)hashmap_get(graph, k);
            order[count] = node->data;
            batches[count]=currentBatch;
            count++;
            // 减少入度
            if (!node) continue;
            // 更新邻接节点入度
            AdjTable* adj = node->adj;
            while (adj) {
                TopoNode* adjNode = hashmap_get(graph, adj->dest);
                if (adjNode && --adjNode->indegree == 0) {
                    enqueue(queue, adj->dest);
                }   
                adj = adj->next;
            }
            
        }
        currentBatch++;
    }
    printf("count:%d\n",count);
    if (count == graph->size)
    {
        result->order = order;
        result->batches = batches;
        result->size = count;
        result->totalBatches = currentBatch;
    }else {
        free(order);
        free(batches);
    }
    
    free(queue);
    return 0;
}


typedef struct {
    char* name;
    int id;
} Task;

void printTask(DataType data) {
    Task* t = (Task*)data;
    printf("%s(id:%d)", t->name, t->id);
}

void hashmap_str_print(HashMap *map) {
    if (!map) return;
    for (size_t i = 0; i < map->capacity; i++) {
        printf("[%d] ", i);
        kvPair *current = map->buckets[i];
        while (current) {
            TopoNode *node = (TopoNode*)current->value;
            Task* task = (Task*)node->data;
            printf("{%s->%d} ", task->name, task->id);
            current = current->next;
        }
        printf("\n");
    }
}

int main() {
    Task tasks[] = {
        {"Initialize", 1},
        {"LoadConfig", 2},
        {"ConnectDB", 3},
        {"StartService", 4},
        {"RunTests", 5},
        {"kkkkkkk",6}
    };

    // 创建hashmap图
    HashMap* graph = hashmap_create(11, 128, sizeof(TopoNode), string_hash, string_compare, NULL, NULL);
    // 添加节点
    for (int i = 0; i < 6; i++) {
        TopoNode* node = (TopoNode*)malloc(sizeof(TopoNode));
        node->data = &tasks[i];
        printf("添加节点：%s -> %d\n", tasks[i].name,tasks[i].id);
        node->indegree = 0;
        node->adj = NULL;
        hashmap_put(graph, tasks[i].name, node);
    }
    // 建立依赖关系
    printf("建立依赖关系:\n");
    addDependence(graph, tasks[0].name, tasks[1].name); // 1 -> 2
    addDependence(graph, tasks[0].name, tasks[2].name); // 1 -> 3
    addDependence(graph, tasks[1].name, tasks[3].name); // 2 -> 4
    addDependence(graph, tasks[2].name, tasks[3].name); // 3 -> 4
    addDependence(graph, tasks[3].name, tasks[4].name); // 4 -> 5
    addDependence(graph, tasks[3].name, tasks[5].name); // 4 -> 6
    addDependence(graph, tasks[4].name, tasks[5].name); // 5 -> 6
    printf("图中节点数量：%d\n", graph->size);
    // hashmap_str_print(graph);
    // 计算拓扑排序
    TopoResult result = {NULL,NULL,0,0};
    topoSort(graph, &result);
    
    hashmap_str_print(graph);
    // 打印结果
    if (result.size == 0)
    {
        printf("图中存在环路！\n");
    }else {
        printf("拓扑排序结果（总批次：%d）:\n", result.totalBatches);
        for (size_t i = 0; i < result.size; i++) {
            printTask(result.order[i]);
            printf(" -> 批次 %d\n", result.batches[i]);
        }
        free(result.order);
        free(result.batches);
    }
    return 0;
}
